package 单调栈;

import java.util.Stack;

/**
 * @PackageName: 单调栈
 * @ClassName: LeetCode901
 * @Author: chen jinxu
 * @Date: 2022/3/13 9:47
 *  编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
 * 今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
 *                      result   1    1    1   2   1   2   3
 *                      stack
 * 例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，
 * 那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
 *
 * 输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
 * 输出：[null,1,1,1,2,1,4,6]
 * 解释：
 * 首先，初始化 S = StockSpanner()，然后：
 * S.next(100) 被调用并返回 1，
 * S.next(80) 被调用并返回 1，
 * S.next(60) 被调用并返回 1，
 * S.next(70) 被调用并返回 2，
 * S.next(60) 被调用并返回 1，
 * S.next(75) 被调用并返回 4，
 * S.next(85) 被调用并返回 6。
 */
public class LeetCode901 {
        private final Stack<Integer> priceStack;
        private final Stack<Integer> widthStack;

        public LeetCode901() {
            this.priceStack = new Stack<>();
            this.widthStack = new Stack<>();
        }

        public int next(int price) {
            int width = 1;
            while (!priceStack.isEmpty() && priceStack.peek() <= price) {
                priceStack.pop();
                width += widthStack.pop();
            }
            priceStack.push(price);
            widthStack.push(width);
            return width;
        }
}
